package seqlist.LeetCode;
//876. 链表的中间结点

/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 */


/**
 * 思路一：简单的办法就是统计长度。如果我们知道链表长度为 n，那么只需要 走 n / 2 步就
 * 会刚好走到中间节点位置
 */

/*

public class Num876_middleNode {
    public ListNode middleNode(ListNode head) {
        int conut = 0;
        //统计链表长度
        for (ListNode x = head; x != null ; x = x.next) {
            conut ++;
        }
        //找到中间节点
        for (int i = 0; i < conut / 2; i++) {
            head = head.next;
        }
        return head;
    }
}

 */


/**
 * 思路二：快慢指针。我们引入两个引用 slow ，fast
 *  slow走一步，fast每次走两步，当 fast走到头的时候，
 *  slow刚好停留在 中间节点上
 */

public class Num876_middleNode {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;


        //只有还有下一个节点存在，指针就可以走两步不报错，
        //一步走到最后节点上，二步走到 null 不影响。
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
